

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="zh" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="zh" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>optuna.multi_objective.samplers._nsga2 &mdash; Optuna 1.4.0 文档</title>
  

  
  
    <link rel="shortcut icon" href="../../../../_static/favicon.ico"/>
  
  
  

  
  <script type="text/javascript" src="../../../../_static/js/modernizr.min.js"></script>
  
    
      <script type="text/javascript" id="documentation_options" data-url_root="../../../../" src="../../../../_static/documentation_options.js"></script>
        <script src="../../../../_static/jquery.js"></script>
        <script src="../../../../_static/underscore.js"></script>
        <script src="../../../../_static/doctools.js"></script>
        <script src="../../../../_static/language_data.js"></script>
        <script async="async" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
    
    <script type="text/javascript" src="../../../../_static/js/theme.js"></script>

    

  
  <link rel="stylesheet" href="../../../../_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="../../../../_static/pygments.css" type="text/css" />
  <link rel="stylesheet" href="../../../../_static/css/custom.css" type="text/css" />
    <link rel="index" title="索引" href="../../../../genindex.html" />
    <link rel="search" title="搜索" href="../../../../search.html" /> 
</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">
    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search" >
          

          
            <a href="../../../../index.html" class="icon icon-home"> Optuna
          

          
          </a>

          
            
            
              <div class="version">
                1.4.0
              </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="../../../../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <p class="caption"><span class="caption-text">目录</span></p>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../../../installation.html">安装</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../../../tutorial/index.html">教程</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../../../reference/index.html">API Reference</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../../../faq.html">常见问题</a></li>
</ul>

            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" aria-label="top navigation">
        
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="../../../../index.html">Optuna</a>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        
          















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="../../../../index.html">Docs</a> &raquo;</li>
        
          <li><a href="../../../index.html">模块代码</a> &raquo;</li>
        
      <li>optuna.multi_objective.samplers._nsga2</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <h1>optuna.multi_objective.samplers._nsga2 源代码</h1><div class="highlight"><pre>
<span></span><span class="kn">from</span> <span class="nn">collections</span> <span class="kn">import</span> <span class="n">defaultdict</span>
<span class="kn">import</span> <span class="nn">itertools</span>
<span class="kn">from</span> <span class="nn">typing</span> <span class="kn">import</span> <span class="n">Any</span>
<span class="kn">from</span> <span class="nn">typing</span> <span class="kn">import</span> <span class="n">DefaultDict</span>
<span class="kn">from</span> <span class="nn">typing</span> <span class="kn">import</span> <span class="n">Dict</span>
<span class="kn">from</span> <span class="nn">typing</span> <span class="kn">import</span> <span class="n">List</span>
<span class="kn">from</span> <span class="nn">typing</span> <span class="kn">import</span> <span class="n">Optional</span>
<span class="kn">from</span> <span class="nn">typing</span> <span class="kn">import</span> <span class="n">Tuple</span>

<span class="kn">import</span> <span class="nn">numpy</span> <span class="k">as</span> <span class="nn">np</span>

<span class="kn">import</span> <span class="nn">optuna</span>
<span class="kn">from</span> <span class="nn">optuna._experimental</span> <span class="kn">import</span> <span class="n">experimental</span>
<span class="kn">from</span> <span class="nn">optuna.distributions</span> <span class="kn">import</span> <span class="n">BaseDistribution</span>
<span class="kn">from</span> <span class="nn">optuna</span> <span class="kn">import</span> <span class="n">multi_objective</span>
<span class="kn">from</span> <span class="nn">optuna.multi_objective.samplers</span> <span class="kn">import</span> <span class="n">BaseMultiObjectiveSampler</span>


<span class="c1"># Define key names of `Trial.system_attrs`.</span>
<span class="n">_GENERATION_KEY</span> <span class="o">=</span> <span class="s2">&quot;multi_objective:nsga2:generation&quot;</span>
<span class="n">_PARENTS_KEY</span> <span class="o">=</span> <span class="s2">&quot;multi_objective:nsga2:parents&quot;</span>


<div class="viewcode-block" id="NSGAIIMultiObjectiveSampler"><a class="viewcode-back" href="../../../../reference/multi_objective/samplers.html#optuna.multi_objective.samplers.NSGAIIMultiObjectiveSampler">[文档]</a><span class="nd">@experimental</span><span class="p">(</span><span class="s2">&quot;1.5.0&quot;</span><span class="p">)</span>
<span class="k">class</span> <span class="nc">NSGAIIMultiObjectiveSampler</span><span class="p">(</span><span class="n">BaseMultiObjectiveSampler</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;Multi-objective sampler using the NSGA-II algorithm.</span>

<span class="sd">    NSGA-II stands for &quot;Nondominated Sorting Genetic Algorithm II&quot;,</span>
<span class="sd">    which is a well known, fast and elitist multi-objective genetic algorithm.</span>

<span class="sd">    For further information about NSGA-II, please refer to the following paper:</span>

<span class="sd">    - `A fast and elitist multiobjective genetic algorithm: NSGA-II</span>
<span class="sd">      &lt;https://ieeexplore.ieee.org/document/996017&gt;`_</span>

<span class="sd">    Args:</span>
<span class="sd">        population_size:</span>
<span class="sd">            Number of individuals (trials) in a generation.</span>

<span class="sd">        mutation_prob:</span>
<span class="sd">            Probability of mutating each parameter when creating a new individual.</span>
<span class="sd">            If :obj:`None` is specified, the value ``1.0 / len(parent_trial.params)`` is used</span>
<span class="sd">            where ``parent_trial`` is the parent trial of the target individual.</span>

<span class="sd">        crossover_prob:</span>
<span class="sd">            Probability that a crossover (parameters swapping between parents) will occur</span>
<span class="sd">            when creating a new individual.</span>

<span class="sd">        swapping_prob:</span>
<span class="sd">            Probability of swapping each parameter of the parents during crossover.</span>

<span class="sd">        seed:</span>
<span class="sd">            Seed for random number generator.</span>

<span class="sd">    &quot;&quot;&quot;</span>

    <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span>
        <span class="bp">self</span><span class="p">,</span>
        <span class="n">population_size</span><span class="p">:</span> <span class="nb">int</span> <span class="o">=</span> <span class="mi">50</span><span class="p">,</span>
        <span class="n">mutation_prob</span><span class="p">:</span> <span class="n">Optional</span><span class="p">[</span><span class="nb">float</span><span class="p">]</span> <span class="o">=</span> <span class="kc">None</span><span class="p">,</span>
        <span class="n">crossover_prob</span><span class="p">:</span> <span class="nb">float</span> <span class="o">=</span> <span class="mf">0.9</span><span class="p">,</span>
        <span class="n">swapping_prob</span><span class="p">:</span> <span class="nb">float</span> <span class="o">=</span> <span class="mf">0.5</span><span class="p">,</span>
        <span class="n">seed</span><span class="p">:</span> <span class="n">Optional</span><span class="p">[</span><span class="nb">int</span><span class="p">]</span> <span class="o">=</span> <span class="kc">None</span><span class="p">,</span>
    <span class="p">)</span> <span class="o">-&gt;</span> <span class="kc">None</span><span class="p">:</span>
        <span class="c1"># TODO(ohta): Reconsider the default value of each parameter.</span>

        <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">population_size</span><span class="p">,</span> <span class="nb">int</span><span class="p">):</span>
            <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s2">&quot;`population_size` must be an integer value.&quot;</span><span class="p">)</span>

        <span class="k">if</span> <span class="n">population_size</span> <span class="o">&lt;</span> <span class="mi">2</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s2">&quot;`population_size` must be greater than or equal to 2.&quot;</span><span class="p">)</span>

        <span class="k">if</span> <span class="ow">not</span> <span class="p">(</span><span class="n">mutation_prob</span> <span class="ow">is</span> <span class="kc">None</span> <span class="ow">or</span> <span class="mf">0.0</span> <span class="o">&lt;=</span> <span class="n">mutation_prob</span> <span class="o">&lt;=</span> <span class="mf">1.0</span><span class="p">):</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span>
                <span class="s2">&quot;`mutation_prob` must be None or a float value within the range [0.0, 1.0].&quot;</span>
            <span class="p">)</span>

        <span class="k">if</span> <span class="ow">not</span> <span class="p">(</span><span class="mf">0.0</span> <span class="o">&lt;=</span> <span class="n">crossover_prob</span> <span class="o">&lt;=</span> <span class="mf">1.0</span><span class="p">):</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s2">&quot;`crossover_prob` must be a float value within the range [0.0, 1.0].&quot;</span><span class="p">)</span>

        <span class="k">if</span> <span class="ow">not</span> <span class="p">(</span><span class="mf">0.0</span> <span class="o">&lt;=</span> <span class="n">swapping_prob</span> <span class="o">&lt;=</span> <span class="mf">1.0</span><span class="p">):</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s2">&quot;`swapping_prob` must be a float value within the range [0.0, 1.0].&quot;</span><span class="p">)</span>

        <span class="bp">self</span><span class="o">.</span><span class="n">_population_size</span> <span class="o">=</span> <span class="n">population_size</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_mutation_prob</span> <span class="o">=</span> <span class="n">mutation_prob</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_crossover_prob</span> <span class="o">=</span> <span class="n">crossover_prob</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_swapping_prob</span> <span class="o">=</span> <span class="n">swapping_prob</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_random_sampler</span> <span class="o">=</span> <span class="n">multi_objective</span><span class="o">.</span><span class="n">samplers</span><span class="o">.</span><span class="n">RandomMultiObjectiveSampler</span><span class="p">(</span><span class="n">seed</span><span class="o">=</span><span class="n">seed</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_rng</span> <span class="o">=</span> <span class="n">np</span><span class="o">.</span><span class="n">random</span><span class="o">.</span><span class="n">RandomState</span><span class="p">(</span><span class="n">seed</span><span class="p">)</span>

    <span class="k">def</span> <span class="nf">infer_relative_search_space</span><span class="p">(</span>
        <span class="bp">self</span><span class="p">,</span>
        <span class="n">study</span><span class="p">:</span> <span class="s2">&quot;multi_objective.study.MultiObjectiveStudy&quot;</span><span class="p">,</span>
        <span class="n">trial</span><span class="p">:</span> <span class="s2">&quot;multi_objective.trial.FrozenMultiObjectiveTrial&quot;</span><span class="p">,</span>
    <span class="p">)</span> <span class="o">-&gt;</span> <span class="n">Dict</span><span class="p">[</span><span class="nb">str</span><span class="p">,</span> <span class="n">BaseDistribution</span><span class="p">]:</span>
        <span class="k">return</span> <span class="p">{}</span>

    <span class="k">def</span> <span class="nf">sample_relative</span><span class="p">(</span>
        <span class="bp">self</span><span class="p">,</span>
        <span class="n">study</span><span class="p">:</span> <span class="s2">&quot;multi_objective.study.MultiObjectiveStudy&quot;</span><span class="p">,</span>
        <span class="n">trial</span><span class="p">:</span> <span class="s2">&quot;multi_objective.trial.FrozenMultiObjectiveTrial&quot;</span><span class="p">,</span>
        <span class="n">search_space</span><span class="p">:</span> <span class="n">Dict</span><span class="p">[</span><span class="nb">str</span><span class="p">,</span> <span class="n">BaseDistribution</span><span class="p">],</span>
    <span class="p">)</span> <span class="o">-&gt;</span> <span class="n">Dict</span><span class="p">[</span><span class="nb">str</span><span class="p">,</span> <span class="n">Any</span><span class="p">]:</span>
        <span class="n">parent_generation</span><span class="p">,</span> <span class="n">parent_population</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_collect_parent_population</span><span class="p">(</span><span class="n">study</span><span class="p">)</span>
        <span class="n">trial_id</span> <span class="o">=</span> <span class="n">trial</span><span class="o">.</span><span class="n">_trial_id</span>

        <span class="n">generation</span> <span class="o">=</span> <span class="n">parent_generation</span> <span class="o">+</span> <span class="mi">1</span>
        <span class="n">study</span><span class="o">.</span><span class="n">_storage</span><span class="o">.</span><span class="n">set_trial_system_attr</span><span class="p">(</span><span class="n">trial_id</span><span class="p">,</span> <span class="n">_GENERATION_KEY</span><span class="p">,</span> <span class="n">generation</span><span class="p">)</span>

        <span class="k">if</span> <span class="n">parent_generation</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">:</span>
            <span class="n">p0</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_select_parent</span><span class="p">(</span><span class="n">study</span><span class="p">,</span> <span class="n">parent_population</span><span class="p">)</span>
            <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">_rng</span><span class="o">.</span><span class="n">rand</span><span class="p">()</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">_crossover_prob</span><span class="p">:</span>
                <span class="n">p1</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_select_parent</span><span class="p">(</span>
                    <span class="n">study</span><span class="p">,</span> <span class="p">[</span><span class="n">t</span> <span class="k">for</span> <span class="n">t</span> <span class="ow">in</span> <span class="n">parent_population</span> <span class="k">if</span> <span class="n">t</span><span class="o">.</span><span class="n">_trial_id</span> <span class="o">!=</span> <span class="n">p0</span><span class="o">.</span><span class="n">_trial_id</span><span class="p">]</span>
                <span class="p">)</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="n">p1</span> <span class="o">=</span> <span class="n">p0</span>

            <span class="n">study</span><span class="o">.</span><span class="n">_storage</span><span class="o">.</span><span class="n">set_trial_system_attr</span><span class="p">(</span>
                <span class="n">trial_id</span><span class="p">,</span> <span class="n">_PARENTS_KEY</span><span class="p">,</span> <span class="p">[</span><span class="n">p0</span><span class="o">.</span><span class="n">_trial_id</span><span class="p">,</span> <span class="n">p1</span><span class="o">.</span><span class="n">_trial_id</span><span class="p">]</span>
            <span class="p">)</span>

        <span class="k">return</span> <span class="p">{}</span>

    <span class="k">def</span> <span class="nf">sample_independent</span><span class="p">(</span>
        <span class="bp">self</span><span class="p">,</span>
        <span class="n">study</span><span class="p">:</span> <span class="s2">&quot;multi_objective.study.MultiObjectiveStudy&quot;</span><span class="p">,</span>
        <span class="n">trial</span><span class="p">:</span> <span class="s2">&quot;multi_objective.trial.FrozenMultiObjectiveTrial&quot;</span><span class="p">,</span>
        <span class="n">param_name</span><span class="p">:</span> <span class="nb">str</span><span class="p">,</span>
        <span class="n">param_distribution</span><span class="p">:</span> <span class="n">BaseDistribution</span><span class="p">,</span>
    <span class="p">)</span> <span class="o">-&gt;</span> <span class="n">Any</span><span class="p">:</span>
        <span class="k">if</span> <span class="n">_PARENTS_KEY</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">trial</span><span class="o">.</span><span class="n">system_attrs</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_random_sampler</span><span class="o">.</span><span class="n">sample_independent</span><span class="p">(</span>
                <span class="n">study</span><span class="p">,</span> <span class="n">trial</span><span class="p">,</span> <span class="n">param_name</span><span class="p">,</span> <span class="n">param_distribution</span>
            <span class="p">)</span>

        <span class="n">p0_id</span><span class="p">,</span> <span class="n">p1_id</span> <span class="o">=</span> <span class="n">trial</span><span class="o">.</span><span class="n">system_attrs</span><span class="p">[</span><span class="n">_PARENTS_KEY</span><span class="p">]</span>
        <span class="n">p0</span> <span class="o">=</span> <span class="n">study</span><span class="o">.</span><span class="n">_storage</span><span class="o">.</span><span class="n">get_trial</span><span class="p">(</span><span class="n">p0_id</span><span class="p">)</span>
        <span class="n">p1</span> <span class="o">=</span> <span class="n">study</span><span class="o">.</span><span class="n">_storage</span><span class="o">.</span><span class="n">get_trial</span><span class="p">(</span><span class="n">p1_id</span><span class="p">)</span>

        <span class="n">param</span> <span class="o">=</span> <span class="n">p0</span><span class="o">.</span><span class="n">params</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="n">param_name</span><span class="p">,</span> <span class="kc">None</span><span class="p">)</span>
        <span class="n">parent_params_len</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">p0</span><span class="o">.</span><span class="n">params</span><span class="p">)</span>
        <span class="k">if</span> <span class="n">param</span> <span class="ow">is</span> <span class="kc">None</span> <span class="ow">or</span> <span class="bp">self</span><span class="o">.</span><span class="n">_rng</span><span class="o">.</span><span class="n">rand</span><span class="p">()</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">_swapping_prob</span><span class="p">:</span>
            <span class="n">param</span> <span class="o">=</span> <span class="n">p1</span><span class="o">.</span><span class="n">params</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="n">param_name</span><span class="p">,</span> <span class="kc">None</span><span class="p">)</span>
            <span class="n">parent_params_len</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">p1</span><span class="o">.</span><span class="n">params</span><span class="p">)</span>

        <span class="n">mutation_prob</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_mutation_prob</span>
        <span class="k">if</span> <span class="n">mutation_prob</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
            <span class="n">mutation_prob</span> <span class="o">=</span> <span class="mf">1.0</span> <span class="o">/</span> <span class="nb">max</span><span class="p">(</span><span class="mf">1.0</span><span class="p">,</span> <span class="n">parent_params_len</span><span class="p">)</span>

        <span class="k">if</span> <span class="n">param</span> <span class="ow">is</span> <span class="kc">None</span> <span class="ow">or</span> <span class="bp">self</span><span class="o">.</span><span class="n">_rng</span><span class="o">.</span><span class="n">rand</span><span class="p">()</span> <span class="o">&lt;</span> <span class="n">mutation_prob</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_random_sampler</span><span class="o">.</span><span class="n">sample_independent</span><span class="p">(</span>
                <span class="n">study</span><span class="p">,</span> <span class="n">trial</span><span class="p">,</span> <span class="n">param_name</span><span class="p">,</span> <span class="n">param_distribution</span>
            <span class="p">)</span>

        <span class="k">return</span> <span class="n">param</span>

    <span class="k">def</span> <span class="nf">_collect_parent_population</span><span class="p">(</span>
        <span class="bp">self</span><span class="p">,</span> <span class="n">study</span><span class="p">:</span> <span class="s2">&quot;multi_objective.study.MultiObjectiveStudy&quot;</span>
    <span class="p">)</span> <span class="o">-&gt;</span> <span class="n">Tuple</span><span class="p">[</span><span class="nb">int</span><span class="p">,</span> <span class="n">List</span><span class="p">[</span><span class="s2">&quot;multi_objective.trial.FrozenMultiObjectiveTrial&quot;</span><span class="p">]]:</span>
        <span class="c1"># TODO(ohta): Optimize this method.</span>

        <span class="n">generation_to_population</span> <span class="o">=</span> <span class="n">defaultdict</span><span class="p">(</span><span class="nb">list</span><span class="p">)</span>
        <span class="k">for</span> <span class="n">trial</span> <span class="ow">in</span> <span class="n">study</span><span class="o">.</span><span class="n">get_trials</span><span class="p">(</span><span class="n">deepcopy</span><span class="o">=</span><span class="kc">False</span><span class="p">):</span>
            <span class="k">if</span> <span class="n">trial</span><span class="o">.</span><span class="n">state</span> <span class="o">!=</span> <span class="n">optuna</span><span class="o">.</span><span class="n">trial</span><span class="o">.</span><span class="n">TrialState</span><span class="o">.</span><span class="n">COMPLETE</span><span class="p">:</span>
                <span class="k">continue</span>

            <span class="n">generation</span> <span class="o">=</span> <span class="n">trial</span><span class="o">.</span><span class="n">system_attrs</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="n">_GENERATION_KEY</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
            <span class="n">generation_to_population</span><span class="p">[</span><span class="n">generation</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">trial</span><span class="p">)</span>

        <span class="n">parent_population</span> <span class="o">=</span> <span class="p">[]</span>  <span class="c1"># type: List[multi_objective.trial.FrozenMultiObjectiveTrial]</span>
        <span class="n">parent_generation</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span>
        <span class="k">for</span> <span class="n">generation</span> <span class="ow">in</span> <span class="n">itertools</span><span class="o">.</span><span class="n">count</span><span class="p">():</span>
            <span class="n">population</span> <span class="o">=</span> <span class="n">generation_to_population</span><span class="p">[</span><span class="n">generation</span><span class="p">]</span>

            <span class="c1"># Under multi-worker settings, the population size might become larger than</span>
            <span class="c1"># `self._population_size`.</span>
            <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">population</span><span class="p">)</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">_population_size</span><span class="p">:</span>
                <span class="k">break</span>

            <span class="n">population</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">parent_population</span><span class="p">)</span>
            <span class="n">parent_population</span> <span class="o">=</span> <span class="p">[]</span>
            <span class="n">parent_generation</span> <span class="o">=</span> <span class="n">generation</span>

            <span class="n">population_per_rank</span> <span class="o">=</span> <span class="n">_fast_non_dominated_sort</span><span class="p">(</span><span class="n">population</span><span class="p">,</span> <span class="n">study</span><span class="o">.</span><span class="n">directions</span><span class="p">)</span>
            <span class="k">for</span> <span class="n">population</span> <span class="ow">in</span> <span class="n">population_per_rank</span><span class="p">:</span>
                <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">parent_population</span><span class="p">)</span> <span class="o">+</span> <span class="nb">len</span><span class="p">(</span><span class="n">population</span><span class="p">)</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">_population_size</span><span class="p">:</span>
                    <span class="n">parent_population</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">population</span><span class="p">)</span>
                <span class="k">else</span><span class="p">:</span>
                    <span class="n">n</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_population_size</span> <span class="o">-</span> <span class="nb">len</span><span class="p">(</span><span class="n">parent_population</span><span class="p">)</span>
                    <span class="n">_crowding_distance_sort</span><span class="p">(</span><span class="n">population</span><span class="p">)</span>
                    <span class="n">parent_population</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">population</span><span class="p">[:</span><span class="n">n</span><span class="p">])</span>
                    <span class="k">break</span>

        <span class="k">return</span> <span class="n">parent_generation</span><span class="p">,</span> <span class="n">parent_population</span>

    <span class="k">def</span> <span class="nf">_select_parent</span><span class="p">(</span>
        <span class="bp">self</span><span class="p">,</span>
        <span class="n">study</span><span class="p">:</span> <span class="s2">&quot;multi_objective.study.MultiObjectiveStudy&quot;</span><span class="p">,</span>
        <span class="n">population</span><span class="p">:</span> <span class="n">List</span><span class="p">[</span><span class="s2">&quot;multi_objective.trial.FrozenMultiObjectiveTrial&quot;</span><span class="p">],</span>
    <span class="p">)</span> <span class="o">-&gt;</span> <span class="s2">&quot;multi_objective.trial.FrozenMultiObjectiveTrial&quot;</span><span class="p">:</span>
        <span class="c1"># TODO(ohta): Consider to allow users to specify the number of parent candidates.</span>
        <span class="n">candidate0</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_rng</span><span class="o">.</span><span class="n">choice</span><span class="p">(</span><span class="n">population</span><span class="p">)</span>
        <span class="n">candidate1</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_rng</span><span class="o">.</span><span class="n">choice</span><span class="p">(</span><span class="n">population</span><span class="p">)</span>

        <span class="c1"># TODO(ohta): Consider crowding distance.</span>
        <span class="k">if</span> <span class="n">candidate0</span><span class="o">.</span><span class="n">_dominates</span><span class="p">(</span><span class="n">candidate1</span><span class="p">,</span> <span class="n">study</span><span class="o">.</span><span class="n">directions</span><span class="p">):</span>
            <span class="k">return</span> <span class="n">candidate0</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">candidate1</span></div>


<span class="k">def</span> <span class="nf">_fast_non_dominated_sort</span><span class="p">(</span>
    <span class="n">population</span><span class="p">:</span> <span class="n">List</span><span class="p">[</span><span class="s2">&quot;multi_objective.trial.FrozenMultiObjectiveTrial&quot;</span><span class="p">],</span>
    <span class="n">directions</span><span class="p">:</span> <span class="n">List</span><span class="p">[</span><span class="n">optuna</span><span class="o">.</span><span class="n">study</span><span class="o">.</span><span class="n">StudyDirection</span><span class="p">],</span>
<span class="p">)</span> <span class="o">-&gt;</span> <span class="n">List</span><span class="p">[</span><span class="n">List</span><span class="p">[</span><span class="s2">&quot;multi_objective.trial.FrozenMultiObjectiveTrial&quot;</span><span class="p">]]:</span>
    <span class="n">dominated_count</span> <span class="o">=</span> <span class="n">defaultdict</span><span class="p">(</span><span class="nb">int</span><span class="p">)</span>  <span class="c1"># type: DefaultDict[int, int]</span>
    <span class="n">dominates_list</span> <span class="o">=</span> <span class="n">defaultdict</span><span class="p">(</span><span class="nb">list</span><span class="p">)</span>

    <span class="k">for</span> <span class="n">p</span><span class="p">,</span> <span class="n">q</span> <span class="ow">in</span> <span class="n">itertools</span><span class="o">.</span><span class="n">combinations</span><span class="p">(</span><span class="n">population</span><span class="p">,</span> <span class="mi">2</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">p</span><span class="o">.</span><span class="n">_dominates</span><span class="p">(</span><span class="n">q</span><span class="p">,</span> <span class="n">directions</span><span class="p">):</span>
            <span class="n">dominates_list</span><span class="p">[</span><span class="n">p</span><span class="o">.</span><span class="n">number</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">q</span><span class="o">.</span><span class="n">number</span><span class="p">)</span>
            <span class="n">dominated_count</span><span class="p">[</span><span class="n">q</span><span class="o">.</span><span class="n">number</span><span class="p">]</span> <span class="o">+=</span> <span class="mi">1</span>
        <span class="k">elif</span> <span class="n">q</span><span class="o">.</span><span class="n">_dominates</span><span class="p">(</span><span class="n">p</span><span class="p">,</span> <span class="n">directions</span><span class="p">):</span>
            <span class="n">dominates_list</span><span class="p">[</span><span class="n">q</span><span class="o">.</span><span class="n">number</span><span class="p">]</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">p</span><span class="o">.</span><span class="n">number</span><span class="p">)</span>
            <span class="n">dominated_count</span><span class="p">[</span><span class="n">p</span><span class="o">.</span><span class="n">number</span><span class="p">]</span> <span class="o">+=</span> <span class="mi">1</span>

    <span class="n">population_per_rank</span> <span class="o">=</span> <span class="p">[]</span>
    <span class="k">while</span> <span class="n">population</span><span class="p">:</span>
        <span class="n">non_dominated_population</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="k">while</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="nb">len</span><span class="p">(</span><span class="n">population</span><span class="p">):</span>
            <span class="k">if</span> <span class="n">dominated_count</span><span class="p">[</span><span class="n">population</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">.</span><span class="n">number</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
                <span class="n">individual</span> <span class="o">=</span> <span class="n">population</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
                <span class="k">if</span> <span class="n">i</span> <span class="o">==</span> <span class="nb">len</span><span class="p">(</span><span class="n">population</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span><span class="p">:</span>
                    <span class="n">population</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
                <span class="k">else</span><span class="p">:</span>
                    <span class="n">population</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">population</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
                <span class="n">non_dominated_population</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">individual</span><span class="p">)</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="n">i</span> <span class="o">+=</span> <span class="mi">1</span>

        <span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="n">non_dominated_population</span><span class="p">:</span>
            <span class="k">for</span> <span class="n">y</span> <span class="ow">in</span> <span class="n">dominates_list</span><span class="p">[</span><span class="n">x</span><span class="o">.</span><span class="n">number</span><span class="p">]:</span>
                <span class="n">dominated_count</span><span class="p">[</span><span class="n">y</span><span class="p">]</span> <span class="o">-=</span> <span class="mi">1</span>

        <span class="k">assert</span> <span class="n">non_dominated_population</span>
        <span class="n">population_per_rank</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">non_dominated_population</span><span class="p">)</span>

    <span class="k">return</span> <span class="n">population_per_rank</span>


<span class="k">def</span> <span class="nf">_crowding_distance_sort</span><span class="p">(</span>
    <span class="n">population</span><span class="p">:</span> <span class="n">List</span><span class="p">[</span><span class="s2">&quot;multi_objective.trial.FrozenMultiObjectiveTrial&quot;</span><span class="p">],</span>
<span class="p">)</span> <span class="o">-&gt;</span> <span class="kc">None</span><span class="p">:</span>
    <span class="n">manhattan_distances</span> <span class="o">=</span> <span class="n">defaultdict</span><span class="p">(</span><span class="nb">float</span><span class="p">)</span>
    <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">population</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">values</span><span class="p">)):</span>
        <span class="n">population</span><span class="o">.</span><span class="n">sort</span><span class="p">(</span><span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="n">x</span><span class="o">.</span><span class="n">values</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>

        <span class="n">v_min</span> <span class="o">=</span> <span class="n">population</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">values</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
        <span class="n">v_max</span> <span class="o">=</span> <span class="n">population</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">.</span><span class="n">values</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
        <span class="k">assert</span> <span class="n">v_min</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span>
        <span class="k">assert</span> <span class="n">v_max</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span>

        <span class="n">width</span> <span class="o">=</span> <span class="n">v_max</span> <span class="o">-</span> <span class="n">v_min</span>
        <span class="k">if</span> <span class="n">width</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">continue</span>

        <span class="n">manhattan_distances</span><span class="p">[</span><span class="n">population</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">number</span><span class="p">]</span> <span class="o">=</span> <span class="nb">float</span><span class="p">(</span><span class="s2">&quot;inf&quot;</span><span class="p">)</span>
        <span class="n">manhattan_distances</span><span class="p">[</span><span class="n">population</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">.</span><span class="n">number</span><span class="p">]</span> <span class="o">=</span> <span class="nb">float</span><span class="p">(</span><span class="s2">&quot;inf&quot;</span><span class="p">)</span>

        <span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="nb">len</span><span class="p">(</span><span class="n">population</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span><span class="p">):</span>
            <span class="n">v_high</span> <span class="o">=</span> <span class="n">population</span><span class="p">[</span><span class="n">j</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]</span><span class="o">.</span><span class="n">values</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
            <span class="n">v_low</span> <span class="o">=</span> <span class="n">population</span><span class="p">[</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span><span class="o">.</span><span class="n">values</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
            <span class="k">assert</span> <span class="n">v_high</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span>
            <span class="k">assert</span> <span class="n">v_low</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span>

            <span class="n">manhattan_distances</span><span class="p">[</span><span class="n">population</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">.</span><span class="n">number</span><span class="p">]</span> <span class="o">+=</span> <span class="p">(</span><span class="n">v_high</span> <span class="o">-</span> <span class="n">v_low</span><span class="p">)</span> <span class="o">/</span> <span class="n">width</span>

    <span class="n">population</span><span class="o">.</span><span class="n">sort</span><span class="p">(</span><span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="n">manhattan_distances</span><span class="p">[</span><span class="n">x</span><span class="o">.</span><span class="n">number</span><span class="p">])</span>
    <span class="n">population</span><span class="o">.</span><span class="n">reverse</span><span class="p">()</span>
</pre></div>

           </div>
           
          </div>
          <footer>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; Copyright 2018, Optuna Contributors.

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
    <a href="../../../../privacy.html">Privacy Policy</a>.
     


</footer>

        </div>
      </div>

    </section>

  </div>
  


  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script>

  
  
    
    <!-- Theme Analytics -->
    <script>
    (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
      (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
      m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
    })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

    ga('create', 'UA-55135190-8', 'auto');
    ga('send', 'pageview');
    </script>

    
   

</body>
</html>